#include<bits/stdc++.h>
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
//#include <immintrin.h>
//#include <emmintrin.h>
#define int long long
#define ls(x) ((x)*2)
#define rs(x) ((x)*2+1)
#define fi first
#define se second
#define pii pair<int,int>
#define Debug(...) fprintf(stderr, __VA_ARGS__)
#define For(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define Rof(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define rep(i,  b) for(int i=1,i##end=b;i<=i##end;i++)
using namespace std;
const int N=1e6+5,base=999983,Mod=998244353;
//char buf[(1<<21)+5],*p1,*p2;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline void chmx(int &x,int y){(x<y)&&(x=y);}
inline void chmn(int &x,int y){(x>y)&&(x=y);}
inline void Add(int &x,int y){(x=x+y+Mod)%=Mod;}
inline int read(){
	int f=0,x=0;
	char ch=getchar();
	while(!isdigit(ch)){f|=(ch=='-');ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return f?-x:x;
}
void print(int n){
    if(n<0){
        putchar('-');
        n*=-1;
    }
    if(n>9) print(n/10);
    putchar(n%10+'0');
}
int n,m,Q;
int fa[N];
set<int>S[N];
int find(int x){
	return (fa[x]==x?x:fa[x]=find(fa[x]));
}
int nxt[N],R[N];
bool vis[N];
int col[N];
int gg[N],cnt=0;
struct Query{
	int l,r,id;
	inline friend bool operator<(Query a,Query b){
		return a.l<b.l;
	}
};int id[N];
set<int>C[N];
vector<Query>q[N],e[N];
int mx[N],tr[N];
inline int lowbit(int x){
	return x&(-x);
} inline void add(int x,int k){
	while(x<=n){tr[x]=min(tr[x],k);x+=lowbit(x);}
}inline int qry(int x){
	int res=1e16;
	while(x){
		res=min(res,tr[x]);
		x-=lowbit(x);
	}return res;
}int answer[N];
signed main(){
	freopen("destory.in","r",stdin);
	freopen("destory.out","w",stdout);
	// ios::sync_with_stdio(false);
	// cin.tie(0); cout.tie(0);
	n=read(),m=read(),Q=read();
	For(i,1,n) fa[i]=i;
	For(i,1,m){
		int x=read(),y=read();
		fa[find(x)]=find(y);
	}
	For(i,1,n){
		col[i]=find(i);
		R[nxt[find(i)]]=i;
		nxt[find(i)]=i;R[i]=n+1;
	}
	int d=0;
	For(i,1,n){
		if(find(i)==i) d++,gg[d]=i,id[i]=d;
	}
	if(n*Q>1000000&&d<=5){
		For(i,1,n){
			C[find(i)].insert(i);
		}
		For(i,1,Q){
			int l=read(),r=read();
			int p=0;
			For(i,1,d){
				auto it=C[gg[i]].lower_bound(l);
				if(it!=C[gg[i]].end()&&(*it)<=r) p|=(1<<(i-1));
			}
			q[p].push_back({l,r,i});
		}
		For(t,1,(1<<d)-1){
			For(i,0,n) vis[i]=0,mx[i]=n+1,e[i].clear(),tr[i]=1e16;
			set<int>S;
			For(i,1,n){
				if(!vis[col[i]]&&(t&(1<<(id[col[i]]-1)))){
					S.insert(i);
					vis[col[i]]=1;
				}
			}
			while(1){
				int x=*S.begin();
				mx[x]=*S.rbegin();
				S.erase(S.begin());
				if(R[x]>n) break;
				S.insert(R[x]);
			}
			for(auto v:q[t]){
				e[v.l].push_back(v);
			}
			Rof(i,n,1){
				if(mx[i]<=n)add(mx[i],mx[i]-i+1);
				for(auto v:e[i]){
					
					answer[v.id]=qry(v.r); 
				}
			}
			
		}
			For(i,1,Q){
				printf("%lld\n",answer[i]);
			}
		return 0;
	}
	while(Q--){
		int l=read(),r=read();
		set<int>S;
		For(i,l,r){
			if(!vis[col[i]]){
				S.insert(i);
				vis[col[i]]=1;
			}
		}
		int ans=r-l+1;
		while(1){
			ans=min(ans,(int)*S.rbegin()-(int)*S.begin()+1);
			int x=*S.begin();
			S.erase(S.begin());
			if(R[x]>r) break;
			S.insert(R[x]);
		}printf("%lld\n",ans);
		For(i,l,r) vis[col[i]]=0;
	}
	
#ifdef LOCAL
    Debug("\nMy Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
#endif
	return 0;
}/*
5 2 5
 2 2
 4 1
 1 1
 1 1
 2 5
 4 5
 3 5
*/

